package com.leetcode.partition3;

import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/12/14 20:46
 */
public class LC207课程表 {

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        return topological(numCourses, prerequisites);
    }

    public static void main(String[] args) {
        int[][] prerequisites = {{1, 0}, {0, 1}};
        int numCourses = 2;
        System.out.println(canFinish(numCourses, prerequisites));
    }

    private static boolean topological(int numCourses, int[][] prerequisites) {
        int answer = 0, index = 0, m = prerequisites.length;
        //邻接表来建图
        int[] head = new int[numCourses], next = new int[m], element = new int[m], inDegree = new int[numCourses];
        for (int i = 0; i < head.length; i++) head[i] = -1;
        for (int[] prerequisite : prerequisites) {
            int v = prerequisite[0], u = prerequisite[1];
            element[index] = v;
            next[index] = head[u];
            head[u] = index++;
            inDegree[v]++;
        }
        //将所有入度为0的结点入队
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            answer++;
            for (int i = head[u]; i != -1; i = next[i]) {
                int v = element[i];
                inDegree[v]--;
                //如果这个结点的入度也是0的话，就加入队列
                if (inDegree[v] == 0) queue.addLast(v);
            }
        }
        return answer == numCourses;
    }
}
